#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define rep(Ii,Jj,Kk) for(int Ii=(Jj),Ii##_=(Kk);Ii<=Ii##_;Ii++)
#define per(Ii,Jj,Kk) for(int Ii=(Jj),Ii##_=(Kk);Ii>=Ii##_;Ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double db;
#define fir first
#define sec second
#define siz(Aa) ((int)(Aa).size())
#define all(Aa) (Aa).begin(),(Aa).end()
#define ckmx(Aa,Bb) (Aa=max(Aa,Bb))
#define ckmn(Aa,Bb) (Aa=min(Aa,Bb))
#define Fi(s) freopen(s,"r",stdin)
#define Fo(s) freopen(s,"w",stdout)
#define Fre(s) Fi(s".in"),Fo(s".out")
bool Mst;
const int N=5010,M=10010,Q=5010;
int n,m,q;
ll a[N],b[N],d[N],c[N][M],tmp[N],ans[N],out[Q];
vector<pair<int,int>> e[N];
bool Med;
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);
#ifdef SuperAnton
	cerr<<(&Mst-&Med)/1048576.<<"MB\n";
#endif
	Fre("clear");
	cin>>n>>m>>q;
	rep(i,1,n) cin>>a[i];
	adjacent_difference(a+1,a+1+n,b+1);
	rep(i,1,n) d[i]=d[i-1]+(b[i]>0?b[i]*(-(i+1)/m):(-b[i])*(i/m));
	rep(i,1,q){
		int l,r;cin>>l>>r;
		out[i]=a[l]*(-(l+1)/m)+a[r]*((r+1)/m)+d[r]-d[l];
		e[r].emplace_back(l,i);	
	}
	rep(i,1,n){
		c[i][(i+1)%m]+=a[i];
		if(b[i]<=0){
			rep(j,1,i-1) tmp[j]-=b[i];
		}
		if(i%m==m-1){
			rep(j,1,i-1) ans[j]+=tmp[j];
		}
		int k=(i+1)%m;
		rep(j,1,i-1){
			ll w=min(tmp[j],c[j][k]);
			c[j][k]-=w;
			tmp[j]-=w;
		}
		if(b[i]>0){
			rep(j,1,i-1) c[j][k]+=b[i];
		}
		for(auto[l,id]:e[i]){
			out[id]+=ans[l];
			ll x=tmp[l]+a[i];
			rep(j,(i+1)%m+1,m-1) x-=c[l][j];
			out[id]+=x;
		}
	}
	rep(i,1,q) cout<<out[i]<<"\n";
return 0;}
/*
1 2 9 7 4 1
3 4 5 6  7  8  9
0 1 2 0  1  2  0
1 2 0 1  2  0  1
1 1 7 -2 -3 -3 -1
*/